{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Steps to Reduce a Number to Zero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfSteps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将数字变成 0 的操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个非负整数&nbsp;<code>num</code>&nbsp;，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = 14\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：\n",
    "</strong>步骤 1) 14 是偶数，除以 2 得到 7 。\n",
    "步骤 2） 7 是奇数，减 1 得到 6 。\n",
    "步骤 3） 6 是偶数，除以 2 得到 3 。\n",
    "步骤 4） 3 是奇数，减 1 得到 2 。\n",
    "步骤 5） 2 是偶数，除以 2 得到 1 。\n",
    "步骤 6） 1 是奇数，减 1 得到 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = 8\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "步骤 1） 8 是偶数，除以 2 得到 4 。\n",
    "步骤 2） 4 是偶数，除以 2 得到 2 。\n",
    "步骤 3） 2 是偶数，除以 2 得到 1 。\n",
    "步骤 4） 1 是奇数，减 1 得到 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = 123\n",
    "<strong>输出：</strong>12\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= num &lt;= 10^6</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-steps-to-reduce-a-number-to-zero](https://leetcode.cn/problems/number-of-steps-to-reduce-a-number-to-zero/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-steps-to-reduce-a-number-to-zero](https://leetcode.cn/problems/number-of-steps-to-reduce-a-number-to-zero/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['14', '8', '123']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps (self, num: int) -> int:\n",
    "        @cache\n",
    "        def f1(val):\n",
    "            if val == 0:\n",
    "                return 0\n",
    "            if val & 1 == 0:\n",
    "                return 1 + f1(val >> 1)\n",
    "            else:\n",
    "                return 1 + f1(val - 1)\n",
    "        return f1(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps (self, num: int) -> int:\n",
    "        step = 0\n",
    "\n",
    "        while num != 0:\n",
    "            end = self.cal(num)\n",
    "            step = step+1\n",
    "            num = end\n",
    "            \n",
    "        return step\n",
    "    \n",
    "    def cal(self, num):\n",
    "        if num%2 == 1:\n",
    "            re = num - 1\n",
    "        else:\n",
    "            re = num/2\n",
    "        return re\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps (self, num: int) -> int:\n",
    "        i = 0\n",
    "        while num:\n",
    "            if num %2 == 0:\n",
    "                num = num/2\n",
    "            else:\n",
    "                num = num - 1\n",
    "            i += 1\n",
    "        return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps(self, num: int) -> int:\n",
    "        total = 0\n",
    "        while num:\n",
    "            total += 1\n",
    "            if num % 2 == 0:\n",
    "                num //= 2\n",
    "            else:\n",
    "                num -= 1\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps (self, num: int) -> int:\n",
    "        step_sum = 0\n",
    "        while num != 0 :\n",
    "            step_sum += 1\n",
    "            if num % 2 == 0:\n",
    "                num = num / 2\n",
    "            else:\n",
    "                num = num - 1\n",
    "        return step_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps (self, num: int) -> int:\n",
    "        count = 0\n",
    "        while num != 0:\n",
    "            if num % 2 == 0:\n",
    "                num //= 2\n",
    "            else:\n",
    "                num -= 1\n",
    "            count += 1\n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps (self, num: int) -> int:\n",
    "        count=0\n",
    "        while num!=0:\n",
    "            count+=1\n",
    "            if num%2==0:\n",
    "                num=num//2\n",
    "                \n",
    "            else:\n",
    "                num=num-1\n",
    "  \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef numberOfSteps (self, num: int) -> int:\n",
    "\t\t# 动态规划（超时）\n",
    "\t\t# if num<3:return num\n",
    "\t\t# dp=[0]*(num+1)\n",
    "\t\t# for i in range(1,num+1):\n",
    "\t\t# \tdp[i]=dp[i>>1]+1 if i&1==0 else dp[i-1]+1\n",
    "\t\t# return dp[num]\n",
    "\t\t# 位运算，奇数的话需要2步将末位变为0\n",
    "\t\tif num==0:return 0\n",
    "\t\ti=0\n",
    "\t\twhile num>0:\n",
    "\t\t\ti+=2 if num&1==1 else 1\n",
    "\t\t\tnum>>=1\n",
    "\t\ti-=1\n",
    "\t\treturn i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps(self, num: int) -> int:\n",
    "        step = 0\n",
    "        while num!=0:\n",
    "            if num%2==0:\n",
    "                num=num/2\n",
    "                step+=1\n",
    "            else:\n",
    "                num-=1\n",
    "                step+=1\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps(self, num: int) -> int:\n",
    "        n = 0\n",
    "        while True:\n",
    "            if num == 0:\n",
    "                return n\n",
    "            if num % 2 == 0:\n",
    "                num = num / 2\n",
    "            else:\n",
    "                num = (num-1)\n",
    "            n+=1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps(self, num: int) -> int:\n",
    "        count = 0\n",
    "        while num > 0:\n",
    "            if (num & 1) == 0:\n",
    "                num >>= 1\n",
    "            else:\n",
    "                num -= 1\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps(self, num: int) -> int:\n",
    "        n = 0\n",
    "        while num > 0:\n",
    "            if num % 2 == 0:\n",
    "                num = num / 2\n",
    "                n +=1\n",
    "            else:\n",
    "                num = (num - 1)\n",
    "                n +=1\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps(self, num: int) -> int:\n",
    "        hash={0:0,1:1}\n",
    "        def f(n:int)->int:\n",
    "            if n in hash:\n",
    "                return hash[n]\n",
    "            if n%2==0:\n",
    "                res=f(n/2)+1\n",
    "            else:\n",
    "                res=f(n-1)+1\n",
    "            hash[n]=res\n",
    "            return res\n",
    "        return f(num)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def numberOfSteps(self, num: int) -> int:\n",
    "        if num < 2:\n",
    "            return num\n",
    "        if num % 2 == 0:\n",
    "            return self.numberOfSteps(num//2) + 1\n",
    "        if num % 2 == 1:\n",
    "            return self.numberOfSteps(num - 1) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps(self, num: int) -> int:\n",
    "        ans = 0\n",
    "        while num != 0:\n",
    "            if num % 2 == 0:\n",
    "                num /= 2\n",
    "            else:\n",
    "                num -= 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps(self, num: int) -> int:\n",
    "        n = 0\n",
    "        while num != 0:\n",
    "            if num % 2 == 0 :\n",
    "                num = num/2\n",
    "            else :\n",
    "                num = num-1\n",
    "            n += 1\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSteps(self, num: int) -> int:\n",
    "        count = 0\n",
    "        while num != 0:\n",
    "            if num % 2 == 0:\n",
    "                num = num / 2\n",
    "                count += 1\n",
    "            elif num % 2 == 1:\n",
    "                num -= 1\n",
    "                count += 1\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
